package LeetCode;

import org.junit.Test;

/**
 * 35. 搜索插入位置
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 *
 * 请必须使用时间复杂度为 O(log n) 的算法。
 *
 * 示例 1:
 *
 * 输入: nums = [1,3,5,6], target = 5
 * 输出: 2
 * 示例 2:
 *
 * 输入: nums = [1,3,5,6], target = 2
 * 输出: 1
 * 示例 3:
 *
 * 输入: nums = [1,3,5,6], target = 7
 * 输出: 4
 * 示例 4:
 *
 * 输入: nums = [1,3,5,6], target = 0
 * 输出: 0
 * 示例 5:
 *
 * 输入: nums = [1], target = 0
 * 输出: 0
 *
 *
 * 提示:
 *
 * 1 <= nums.length <= 104
 * -104 <= nums[i] <= 104
 * nums 为无重复元素的升序排列数组
 * -104 <= target <= 104
 * 通过次数499,388提交次数1,075,879
 */
public class Code35 {
    public int searchInsert(@org.jetbrains.annotations.NotNull int[] nums, int target) { // 二分查找法
        if (target <= nums[0]) // 排除例外情况，题中已说明nums.length!=0
            return 0;
        if (nums[nums.length-1] < target) // 这里有毒，相同的数，返回他的索引
            return nums.length;
        if (nums[nums.length-1] == target)
            return nums.length - 1;

        int begin = 0;
        int end = nums.length - 1;
        while (end - begin > 1){
            int t = (end - begin)/2 + begin;
//            int t = (end - begin)>>1 + begin;
            if (nums[t] < target)
                begin = t;
            else if(target < nums[t])
                end = t;
            else if (target == nums[t])
                return t;
        }

        return begin + 1;
    }

    @Test
    public void test1(){
        Code35 code35 = new Code35();
        System.out.println("code35.searchInsert(new int[]{1,3},3) = " + code35.searchInsert(new int[]{1, 3}, 3));
        System.out.println("code35.searchInsert(new int[]{1,3,5,6},7) = " + code35.searchInsert(new int[]{1, 3, 5, 6}, 7));
        System.out.println("code35.searchInser,t(new int[]{1},0) = " + code35.searchInsert(new int[]{1}, 0));
        System.out.println("code35.searchInsert(new int[]{1,3,5,6},2) = " + code35.searchInsert(new int[]{1, 3, 5, 6}, 2));
        System.out.println("code35.searchInsert(new int[]{1,3,5,6},5) = " + code35.searchInsert(new int[]{1, 3, 5, 6}, 5));
    }
}
